package org.example.dp.bidimensional;

/**
 * @Description: TODO
 *
 * 题目描述
 * 给定一个二维的 0-1 矩阵，求全由 1 构成的最大正方形面积。
 * 输入输出样例
 * 输入是一个二维 0-1 数组，输出是最大正方形面积。
 * Input:
 * [["1","0","1","0","0"],
 * ["1","0","1","1","1"],
 * ["1","1","1","1","1"],
 * ["1","0","0","1","0"]]
 * Output: 4
 *
 * @Author wyatt
 * @Data 2024/05/13 15:53
 */
public class Solution221 {

    public static void main(String[] args) {
        Solution221 solution222 = new Solution221();

        char[][] grid = {
                {1,0,1,0,0},
                {1,0,1,1,1},
                {1,1,1,1,1},
                {1,0,0,1,0}
        };

        System.out.println(solution222.test(grid));
    }

    public int test(char[][] matrix) {

        int maxSide = 0;

        int[][] grid = new int[matrix.length][matrix[0].length];
        for(int i=0;i<grid.length;i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if(matrix[i][j] == '1'){
                    grid[i][j] = 1;
                    maxSide = 1;
                }else {
                    grid[i][j] = 0;
                }
                System.out.print(grid[i][j] + " ");
            }
            System.out.println(); // 每行结束后换行
        }


        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[i].length;j++){
                if(grid[i][j] == 1){
                    int baseSide = grid[i-1][j-1];
                    if(baseSide > 0){
                        grid[i][j] = Math.min(grid[i-1][j-1], Math.min(grid[i-1][j], grid[i][j-1])) + 1;
                        maxSide = Math.max(maxSide, grid[i][j]);
                    }
                }
            }
        }

        return maxSide*maxSide;
    }

}
